|
In the two–party communication game, introduced by ,〔.〕 two players, ''P''1 and ''P''2 attempt to compute a Boolean function : Player ''P''1 knows the value of ''x''2, ''P''2 knows the value of ''x''1, but ''P''''i'' does not know the value of ''x''''i'', for ''i'' = 1, 2. In other words, the players know the other's variables, but not their own. The minimum number of bits that must be communicated by the players to compute ''f'' is the communication complexity of ''f'', denoted by ''κ''(''f''). The multiparty communication game, defined in 1983,〔.〕 it is a powerful generalization of the 2–party case: Here the players know all the others' input, except their own. Because of this property, sometimes this model is called "numbers on the foreheadˇ model, since if the players were seated around a roundtable, each wearing their own input on the forehead, then every player would see all the others' input, except their own. The formal definition is as follows: ''k'' players: ''P''1,''P''2,...,''P''''k'' intend to compute a Boolean function : On set ''S'' = of variables there is a fixed partition ''A'' of ''k'' classes ''A''1,''A''2,...,''A''''k'', and player ''P''1 knows every variable, ''except'' those in ''A''''i'', for ''i'' = 1,2,...,''k''. The players have unlimited computational power, and they communicate with the help of a blackboard, viewed by all players. The aim is to compute ''f''(''x''1,''x''2,...,''x''''n''), such that at the end of the computation, every player knows this value. The cost of the computation is the number of bits written onto the blackboard for the given input ''x'' = (''x''1,''x''2,...,''x''''n'') and partition ''A'' = (''A''1,''A''2,...,''A''''k''). The cost of a multiparty protocol is the maximum number of bits communicated for any ''x'' from the set ''n'' and the given partition ''A''. The ''k''-party communication complexity, ''C''(''k'')''A''(''f''), of a function ''f'', with respect to partition ''A'', is the minimum of costs of those ''k''-party protocols which compute ''f''. The ''k''-party symmetric communication complexity of ''f'' is defined as : where the maximum is taken over all ''k''-partitions of set ''x'' = (''x''1,''x''2,...,''x''''n''). == Upper and lower bounds == For a general upper bound both for two and more players, let us suppose that ''A''1 is one of the smallest classes of the partition ''A''1,''A''2,...,''A''''k''. Then ''P''1 can compute any Boolean function of ''S'' with |''A''1| + 1 bits of communication: ''P''2 writes down the |''A''1| bits of ''A''1 on the blackboard, ''P''1 reads it, and computes and announces the value ''f''(''x''). So, we can write: : The Generalized Inner Product function (GIP)〔.〕 is defined as follows: Let ''y''1,''y''2,...,''y''''k'' be ''n''-bit vectors, and let ''Y'' be the ''n'' times ''k'' matrix, with k columns as the ''y''1,''y''2,...,''y''''k'' vectors. Then GIP(''y''1,''y''2,...,''y''''k'') is the number of the all-1 rows of matrix ''Y'', taken modulo 2. In other words, if the vectors ''y''1,''y''2,...,''y''''k'' correspond to the characteristic vectors of ''k'' subsets of an ''n'' element base-set, then GIP corresponds to the parity of the intersection of these ''k'' subsets. It was shown〔 that : with a constant ''c'' > 0. An upper bound to the multiparty communication complexity of GIP shows〔.〕 that " with a constant ''c'' > 0. For a general Boolean function ''f'', one can bound the multiparty communication complexity of ''f'' by using its ''L''1 norm〔.〕 as follows〔.〕 : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Multiparty communication complexity」の詳細全文を読む スポンサード リンク
|